1. Field of the Invention
The present invention relates to a method, system, and article of manufacture for using different algorithms to destage different types of data from cache.
2. Description of the Related Art
A cache management system returns complete to a write request when the received write data directed to a storage device is written to cache and before the write data is written out to the storage device, such as a hard disk drive. The write latency to the storage device is typically significantly longer than the latency to write to a cache memory. Consequentially, returning complete before the write data is written to the storage device reduces write latency and returns complete faster than if complete is returned after writing the data to the storage device.
A cache management system may maintain a linked list having one entry for each data unit stored in the cache, which may comprise write data buffered in cache before writing to the storage device or read data. In the commonly used Least Recently Used (LRU) cache technique, if data in the cache is accessed, i.e., a cache “hit”, then the entry in the LRU list for the accessed data is moved to a Most Recently Used (MRU) end of the list. If the requested data is not in the cache, i.e., a cache miss, then the data in the cache whose entry is at the LRU end of the list may be removed (or destaged back to storage) and an entry for the new data staged into cache is added to the MRU end of the LRU list. With this LRU cache technique, data that is more frequently accessed is likely to remain in cache, while data less frequently accessed will more likely be removed from the LRU end of the list to make room in cache for newly accessed data.
The LRU cache technique seeks to optimize for temporal locality so as to destage data that is least likely to be rewritten soon in order to minimize the number of destage operations, i.e., if a write that is not destaged is overwritten than the destaging of the overwritten write is avoided, thus saving the time and effort of writing the data from cache to disk. On the other hand there is also a desire to destage in a manner that exploits spatial locality, which means that data is written to storage locations that are closest to each other to minimize the distance the storage device write mechanism and storage media needs to be moved to reach the next storage location to write.
One technique for exploiting both temporal and spatial locality is the Wise Ordering for Writes (WOW) algorithm. The WOW algorithm employs a circular linked list or clock where the circular linked list has one entry for each write request buffered in cache. The entries are ordered in the linked list according to the storage location to which the associated write request is directed to exploit the benefits of spatial locality. Further, each entry includes a bit indicating whether the write data for the storage location in the cache has been recently updated. The bit for an entry is set when the write data for the entry is updated. A pointer points to a current entry in the circular linked list. A task using the WOW algorithm accesses an entry addressed by the pointer. If the bit for the entry indicates that the data for the entry in cache has been recently updated, then the bit is set to indicate that the write data has not been recently updated and the pointer incremented to point to the next entry so that the entry having write data to a storage location next closest in spatial proximity to the previously written storage location is considered. The entry is selected to write that is closest in spatial proximity to the last written storage location and whose bit indicates that the write data for the entry has not recently been updated.
Thus, with the WOW algorithm, spatial locality is exploited because a next entry to write is selected for consideration that is closest in spatial proximity to the last destaged write request. Further, temporal locality is exploited because an entry that has recently been written will be skipped until the pointer circles back to that skipped entry to consider.